package interview.kparentheses;

import java.util.ArrayList;
import java.util.Iterator;

public class Kparentheses {
	public int run(int k) {
		return printParentheses(k).size();
	}

	private ArrayList<String> printParentheses(int k) {
		if(k == 0) {
			ArrayList<String> r = new ArrayList<String>();
			r.add("");
			return r;
		}
		
		if(k == 1) {
			ArrayList<String> r = new ArrayList<String>();
			r.add("()");
			return r;
		}
		
		ArrayList<String> left, right, result;
		result = new ArrayList<String>();
		for(int i = 0; i < k; i++) {
			left = printParentheses(i);
			right = printParentheses(k - i - 1);
			Iterator<String> ileft = left.iterator();
			while(ileft.hasNext()) {
				String next = ileft.next();
				Iterator<String> iright = right.iterator();
				while(iright.hasNext()) {
					result.add("(" + next + ")" + iright.next());
				}
			}
		}
		return result;
	}
}
